#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef NMAX
#define NMAX 100000
#endif

struct Node {
	int key;
	Node *prev, *next;
};

struct List {
	Node nodes[NMAX+1];
	Node *begin, *end;
	Node *freeTop;
};


void
Init(List *lst)
{
	struct Node *node = &lst->nodes[0];
	node->prev = node;
	node->next = node;
	lst->begin = node;
	lst->end   = node;

	lst->freeTop = &lst->nodes[1];
	for (register int i = 1 ; i < NMAX ; ++i)
		lst->nodes[i].next = &lst->nodes[i+1];
	lst->nodes[NMAX].next = NULL;
}

struct Node*
Insert(List *lst, Node *node, int key)
{
	struct Node *newNode = lst->freeTop;
	lst->freeTop  = lst->freeTop->next;

	newNode->key  = key;
	newNode->prev = node->prev;
	newNode->next = node;

	newNode->prev->next = newNode;
	node->prev          = newNode;

	if (node == lst->begin)
		lst->begin = newNode;

	return newNode;
}

unsigned char
IsEmpty(const List *lst)
{
	return lst->begin->next == lst->end;
}

struct Node*
Delete(List * lst, Node * node)
{
	struct Node *nx = node->next,
		    *pr = node->prev;
	node->next   = lst->freeTop;
	lst->freeTop = node;
	pr->next = nx;
	nx->prev = pr;
	if (node == lst->begin)
		lst->begin = nx;
	return nx;
}


/*char *commands[] = {
	"Begin",
	"End",
	"Next",
	"Prev",
	"Delete",
	"Insert",
	"Print",
};*/


int
main(void)
{
	static struct List l;
	struct Node *ptr = NULL;
	register struct Node *ptr_;
	static char line[21];
	int key = 0;

	Init(&l);
	ptr = l.end->next;

	/* {{{ */
	/*
	ptr_ = l.begin;
	(void) fprintf(stderr, " line: \"%s\"\n", line);
	(void) fprintf(stderr, "  ptr=%p[%3ld], ptr->key=%d\n", ptr, (ptr - &l.nodes[0]), ptr->key);
	while (ptr_ != l.end) {
		(void) fprintf(stderr, "{ prev=%3ld key=%5d next=%3ld }[%ld]\n",
				(ptr_->prev - &l.nodes[0]),
				ptr_->key,
				(ptr_->next - &l.nodes[0]),
				(ptr_ - &l.nodes[0]) );
		ptr_ = ptr_->next;
	}
	(void) fprintf(stderr, " l.begin=%3ld,\n l.end=%3ld,\n "
			"l.end->prev=%3ld,\n l.end->next=%3ld,\n l.freeTop=%3ld\n",
			(l.begin - &l.nodes[0]), (l.end - &l.nodes[0]),
			(l.end->prev - &l.nodes[0]), (l.end->next - &l.nodes[0]),
			(l.freeTop - &l.nodes[0]) );
	putc('\n', stderr);
	*/
	/* }}} */
	while (scanf("%s", line) == 1) {
		if (!strcmp(line, "Begin"))
		{
			ptr = l.begin;
		} 
		else if (!strcmp(line, "End"))
		{
			ptr = l.end;
		}
		else if (!strcmp(line, "Next"))
		{
			ptr = ptr->next;
		}
		else if (!strcmp(line, "Prev"))
		{
			ptr = ptr->prev;
		}
		else if (!strcmp(line, "Delete"))
		{
			ptr = Delete(&l, ptr);
		}
		else if (!strcmp(line, "Insert"))
		{
			(void) scanf("%d", &key);
			Insert(&l, ptr, key);
		}
		else if (!strcmp(line, "Print"))
		{
			(void) printf("%d\n", ptr->key);
		} else
			(void) fprintf(stderr, "unrecognized cmd: %s", line);

		/*
		ptr_ = l.begin;
		(void) fprintf(stderr, " line: \"%s\"\n", line);
		(void) fprintf(stderr, "  ptr=%p[%3ld], ptr->key=%d\n", ptr, (ptr - &l.nodes[0]), ptr->key);
		while (ptr_ != l.end) {
			(void) fprintf(stderr, "{ prev=%3ld key=%5d next=%3ld }[%ld]\n",
					(ptr_->prev - &l.nodes[0]),
					ptr_->key,
					(ptr_->next - &l.nodes[0]),
					(ptr_ - &l.nodes[0]) );
			ptr_ = ptr_->next;
		}
		(void) fprintf(stderr, " l.begin=%3ld,\n l.end=%3ld,\n "
				"l.end->prev=%3ld,\n l.end->next=%3ld,\n l.freeTop=%3ld\n",
				(l.begin - &l.nodes[0]), (l.end - &l.nodes[0]),
				(l.end->prev - &l.nodes[0]), (l.end->next - &l.nodes[0]),
				(l.freeTop - &l.nodes[0]) );
		putc('\n', stderr);
		*/
	}
	return 0;
}
// vim:foldmethod=marker:
